package com.offer;

import com.bean.TreeNode;
import com.bean.TreeOperationUtils;
import com.sun.source.tree.Tree;

import java.util.HashMap;
import java.util.Map;

public class Test7 {

//    前序遍历 preorder = [3,9,20,15,7]
//    中序遍历 inorder = [9,3,15,20,7]

    private Map<Integer, Integer> indexMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = inorder.length;
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }

        return buildMyTree(preorder, 0, n - 1, 0);
    }

    private TreeNode buildMyTree(int[] preorder, int preorderLeft, int preorderRight, int inorderLeft) {
        if (preorderLeft > preorderRight) {
            return null;
        }

        int inorderRootIndex = indexMap.get(preorder[preorderLeft]);

        int inorderLeftSize = inorderRootIndex - inorderLeft;

        TreeNode node = new TreeNode(preorder[preorderLeft]);

        node.left = buildMyTree(preorder, preorderLeft + 1, preorderLeft + inorderLeftSize, inorderLeft);
        node.right = buildMyTree(preorder, preorderLeft + inorderLeftSize + 1, preorderRight, inorderLeft + inorderLeftSize + 1);

        return node;
    }

    public static void main(String[] args) {
        int[] preorder = new int[]{3, 9, 20, 15, 7, 6};
        int[] inorder = new int[]{9, 3, 15, 20, 7, 6};

        Test7 test7 = new Test7();
        TreeNode root = test7.buildTree(preorder, inorder);

        TreeOperationUtils.show(root);
    }

}
